#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

class Solution {
    int f[10];
public:
    void dfs(int u, int c, int k, int n, vector<vector<int>>& res)
    {
        if (u == k)
        {
            int sum = 0;
            for (int i = 0; i < u; i++)    sum += f[i];
            if (sum == n)
            {
                vector<int> t;
                for (int i = 0; i < u; i++)    t.push_back(f[i]);
                res.push_back(t);
            }
        }

        for (int i = c + 1; i <= 9; i++)
        {
            f[u] = i;
            dfs(u + 1, i, k, n, res);
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        dfs(0, 0, k, n, res);
        return res;
    }
};